排序
- 直接插入排序
- 希尔排序
- 冒泡排序
- 快速排序
- 选择排序
- 堆排序
- 归并排序
- 计数排序
- 桶排序
- 基数排序
直接插入排序:选取无序区的一个元素找到在有序区的插入位置,插入有序区(排扑克牌的过程)
- 平均时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 稳定性:稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* 插入排序
* @param arr
*/
public void insertSort(int[] arr) {
//初始第一个元素为有序区,第二个数开始作为无序区,逐渐缩小无序区,扩大有序区
for (int i = 1; i < arr.length; i++) {
int val = arr[i];//每轮取无序区第一个数作为待插入元素
int j=i-1;//有序区最后
//寻找插入位置索引,在有序区最后从后往前检索
while (j>=0&&val<arr[j]){
arr[j+1]=arr[j];
j--;
}
//找到插入位置
if (j != i - 1) {
arr[j + 1] = val;
}
}
}
希尔排序(缩小增量法):(直接插入排序优化)先选定一个整数gap(步长),把待排序序列中所有元素(n个)分成gap个组,所有距离为gap的元素分在同一组内,并对每一组内的元素进行直接插入排序。然后将gap逐渐减小,重复上述分组和排序的工作,当到达gap=1时,排序前的数据已将近正序,所有元素在统一组内排好序,gap=0时结束。(效率高于直接插入排序,但不稳定)
- 平均时间复杂度:O(nlogn)
- 空间复杂度:O(1)
- 稳定性:不稳定
取gap=n/2为例:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public void shellSort(int[] arr) {
for (int gap = arr.length >> 1; gap > 0; gap = gap >> 1) {//缩小步长
//直接插入排序(原直接插入排序相当于步长为1的情况,所以对原插入排序有1的地方改为gap即可)
for (int i = gap; i < arr.length; i++) {
int val = arr[i];
int j=i-gap;
while (j>=0&&val<arr[j]){
arr[j+gap]=arr[j];
j-=gap;
}
if (j != i - gap) {
arr[j + gap] = val;
}
}
}
}
冒泡排序:每一轮从头开始,从前往后两两元素进行比较,前一个比后一个大就交换,直到将最大的元素交换到末尾位置,每轮减少一个元素
- 平均时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 稳定性:稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* 冒泡排序
* @param arr
*/
public void bubbleSort(int[] arr){
boolean isSwap=false;//看一轮中是否交换过元素,如果没交换过,则说明序列有序,不用进行后面的轮
for (int i = 0; i < arr.length-1; i++) {//最后一轮只剩一个元素,不用进行
for (int j = 0; j < arr.length - i-1; j++) {//每轮最后一个元素不用往后比较
if (arr[j]>arr[j+1]){
swap(arr,j,j+1);
isSwap=true;
}
}
if (!isSwap){
break;
}
isSwap=false;
}
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
快速排序:基于分治思想排序,将某元素作为基准值,把比基准值小的调整到基准值左边,递归切分基准值左右两部分,按同样规则进行调整
- 平均时间复杂度:O(nlogn)
- 空间复杂度:O(logn)
- 稳定性:不稳定
调整具体思路是:
- 选定一个基准值(为了方便选区间最左边那个)
- 确定两个指针 l 和 r,分别从区间两边向中间走,r指针找比基准值小的,l指针找比基准值大的,指针移动时,让r指针先走
- 两指针停下后交换对应位置的值
- 继续向下走,重复以上步骤,直到两指针重合时,最后将基准值与重合位置值进行交换。
为什么要让r指针先走?
最后是要把相遇位置处的数和基准位置处的数进行交换,要保证交换到基准值位置的数比基准值小,如果让l指针(找大的)先走,l指针先停下,两指针相遇时会找到一个比基准值大的数和基准值交换,所以得让r指针(找小的)先走
[6,1,2,7,9,3,4,5,10,8]调整过程:
完整快速排序过程:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
* 快速排序
* @param arr
*/
public void quickSort(int[] arr){
split(arr,0,arr.length-1);
}
/**
* 切分
* @param arr
* @param left
* @param right
*/
private void split(int[] arr,int left,int right){
if (left>=right){
return;
}
int p=partition(arr,left,right);
split(arr,left,p-1);//切分基准值左半部分
split(arr,p+1,right);//切分基准值右半部分
}
/**
* 小于基准值的调整到基准值左边
* @param arr
* 区间
* @param left
* @param right
* @return 交换后的基准值索引
*/
private int partition(int[] arr, int left, int right) {
int i=left;
int j=right;
int pv=arr[left];//每次为区间最左边的那个
while (i<j){
while (i<j&&arr[j]>pv){//找比基准值小的
j--;
}
while (i<j&&arr[i]<=pv){//找比基准值大的
i++;
}
swap(arr,i,j);
}
swap(arr,left,i);
return i;
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
选择排序:每轮在区间中选择一个最小的排在该轮区间最前面
- 平均时间复杂度:O(n^2)
- 空间复杂度:O(1)
- 稳定性:不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
* 选择排序
* @param arr
*/
public void selectSort(int[] arr){
for (int i = 0; i < arr.length; i++) {
int min = findMin(arr, i);
swap(arr,i,min);
}
}
/**
* @param arr
* @param left
* @return 数组区间从[left~最后一个元素]最小值索引
*/
private int findMin(int[] arr,int left){
int minVal=arr[left];
int minIndex=left;
for (int i = left+1; i <arr.length; i++) {
if (minVal>arr[i]){
minVal=arr[i];
minIndex=i;
}
}
return minIndex;
}
/**
* 交换
* @param arr
* @param i
* @param min
*/
private void swap(int[] arr, int i, int min) {
int temp=arr[i];
arr[i]=arr[min];
arr[min]=temp;
}
- 堆排序:每轮将待排的无序序列调整成堆结构,将堆顶最值交换到最后,每轮减少一个元素
基本思路:
- 升序采用大顶堆(由于大根堆每轮最大的会被交换到最后,形成升序序列),降序采用小顶堆
- 首先将待排序的数组调整成一个堆(大根堆/小根堆),此时,整个数组的最大(小)值就是堆顶
- 将堆顶元素与末尾的元素交换,此时,末尾的元素为最大(小)值,剩余待排序序列个数为n-1个
- 将剩余的n-1个数再调整成堆(大根堆/小根堆),由于交换后只有堆顶元素不符合堆结构,所以对堆顶元素执行下潜即可,再将堆顶元素与n-1位置的元素交换,如此反复执行,便能得到有序序列
平均时间复杂度:O(nlogn)
空间复杂度:O(1)
稳定性:不稳定
堆:一种完全二叉树
- 大顶堆:每个父结点的值都大于其左右孩子的值
- 小顶堆:每个父结点的值都小于其左右孩子的值
数组表示:
数组中某个元素的父结点及其左右孩子索引:
- 父节点索引为i
- 左孩子索引:2*i+1
- 右孩子索引:2*i+2(左孩子索引+1)
- 左孩子索引为j
- 父节点索引:(j-1)/2
- 最后一个非叶子结点索引:数组长度/2-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59/**
* 堆排序
* @param arr
*/
public void heapSort(int[] arr){
heapify(arr);//建堆
int size=arr.length;
while (size>1){//交换堆顶元素和末尾元素
swap(arr,0,size-1);
size--;
down(arr,0,size);//重新调整堆结构
}
}
/**
* 建堆
* @param arr
*/
private void heapify(int[] arr) {
//从后往前第一个非叶子结点开始下潜(弗洛伊德建堆O(logn))(另一种威廉姆斯建堆,边添加结点边调整堆结构O(nlogn))
for (int i = arr.length / 2 - 1; i >=0 ; i--) {
down(arr,i,arr.length);
}
}
/**
* 下潜
* @param arr
* @param i 开始结点索引
* @param n 结束索引
*/
private void down(int[] arr, int i,int n) {
int max=i;
int left=i*2+1;//左孩子索引
int right=left+1;//右孩子索引
//父节点和左右孩子中选一个最大的(大顶堆)(若选最小的为小顶堆)
if (left<n&&arr[max]<arr[left]){
max=left;
}
if (right<n&&arr[max]<arr[right]){
max=right;
}
if (max!=i){
swap(arr,i,max);
down(arr,max,n);//继续下潜
}
}
/**
* 交换
* @param arr
* @param i
* @param j
*/
private void swap(int[] arr, int i, int j) {
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
归并排序:基于分治思想的排序算法
- 思想
- 分:切分原始数组(向下)
- 治:两子序列合并成有序序列
- 合:有序序列继续和其他序列合并(向上)
- 平均时间复杂度:O(nlogn)
- 空间复杂度:O(n)
- 稳定性:稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/**
* 归并排序
* @param arr
*/
public void mergeSort(int[] arr){
if (arr.length==0){
return;
}
int[] temp=new int[arr.length];
split(arr,0,arr.length-1,temp);
}
/**
* 切分
* @param arr
* @param left 左边界
* @param right 右边界
* @param temp 临时数组,合并时用
*/
private void split(int[] arr, int left, int right,int[] temp) {
if (left==right){
return;
}
int mid=left+right>>>1;
split(arr,left,mid,temp);//左半部分切分
split(arr,mid+1,right,temp);//右半部分切分
merge(arr,left,mid,mid+1,right,temp);//合并成有序序列(结果在临时数组中)
System.arraycopy(temp,left,arr,left,right-left+1);//合并结果存回原数组,继续合并
}
/**
* 合并(数组两区间合并成有序序列存于临时数组中)
* @param arr
* @param left
* @param leftEnd
* @param right
* @param rightEnd
* @param temp
*/
private void merge(int[] arr, int left, int leftEnd, int right, int rightEnd,int[] temp) {
int i=left;
int j=right;
int k=left;
while (i<=leftEnd&&j<=rightEnd){
if (arr[i]<arr[j]){
temp[k]=arr[i];
i++;
}else {
temp[k]=arr[j];
j++;
}
k++;
}
if (j>rightEnd){
System.arraycopy(arr,i,temp,k,leftEnd-i+1);
}
if (i>leftEnd){
System.arraycopy(arr,j,temp,k,rightEnd-j+1);
}
}- 思想
计数排序:使用一个count[]数组来统计原数组每个元素出现的个数,count数组值作为元素个数值,索引作为元素值(索引和元素值之间的关系为相对值,不一定与元素值相等,建立一种映射关系),再根据个数把对应元素写回原数组
- 平均时间复杂度:O(n+k) (k为count[]大小,n元素个数)
- 空间复杂度:O(k)
- 稳定性:可稳定或不稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* 只针对元素大于0计数排序(可通过此理解和改写成通用版本)
* @param arr
*/
public void countSort(int[] arr){
//求最大
int max=arr[0];
for (int i = 0; i < arr.length; i++) {
if (max<arr[i]){
max=arr[i];
}
}
//计数数组
int[] count=new int[max+1];
//统计元素个数
for (int i : arr) {
count[i]++;
}
//写回原数组
int j=0;
for (int i = 0; i < count.length; i++) {
while (count[i]>0){
arr[j++]=i;
count[i]--;
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* 计数排序
* @param arr
*/
public void countSort(int[] arr){
//求最大最小值
int max=arr[0];
int min=arr[0];
for (int i = 0; i < arr.length; i++) {
if (max<arr[i]){
max=arr[i];
}
if (min>arr[i]){
min=arr[i];
}
}
//计数数组
int[] count=new int[max-min+1];
//统计元素个数
for (int i : arr) {
count[i-min]++;
}
//写回原数组
int j=0;
for (int i = 0; i < count.length; i++) {
while (count[i]>0){
arr[j++]=i+min;
count[i]--;
}
}
}
- 桶排序:将数组元素分散到多个桶,保证索引小的桶装小的元素,索引大的桶装大的元素,然后进行桶内排序后,接着按顺序取桶,最后把桶内元素写回原数组
平均时间复杂度:O(n+k) (k为桶个数,n为元素个数)
空间复杂度:O(n+k)
稳定性:稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41/**
* 桶排序(此版本结合计数排序方便理解和改进)
* @param arr
*/
public void bucketSort(int[] arr){
//求最大值和最小值,max-min得数据范围
int max=arr[0];
int min=arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i]>max){
max=arr[i];
}
if (arr[i]<min){
min=arr[i];
}
}
//初始化桶(max-min+1为数据范围内的每个数分配一个桶)
ArrayList[] buckets=new ArrayList[max-min+1];
for (int i = 0; i < buckets.length; i++) {
buckets[i]=new ArrayList();
}
//将数组元素分散到桶(元素值-min可以分配到对应桶且桶内元素只有一个,元素和桶具有映射关系
// ->和计数排序类似,这样保证了小桶装小元素,大桶装大元素,因为只有一个元素,所以可以不用进行桶内排序
// 所以按顺序取桶,写元素即可,但空间浪费大)
for (int i : arr) {
buckets[i-min].add(i);
}
int k=0;
for (ArrayList bucket : buckets) {
//桶内排序
//bucket.sort(Comparator.comparingInt(o -> (Integer) o));
//将桶内元素放回原数组
for (Object o : bucket) {
arr[k]= (int) o;
k++;
}
}
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43/**
* 桶排序(改进版)
* @param arr
* @param range 控制桶的数量和桶内元素个数
*/
public void bucketSort(int[] arr,int range){
//求最大值和最小值,max-min得数据范围
int max=arr[0];
int min=arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i]>max){
max=arr[i];
}
if (arr[i]<min){
min=arr[i];
}
}
//初始化桶(max-min+1为数据范围内的每个数分配一个桶) (除range减少桶数量)
ArrayList[] buckets=new ArrayList[(max-min)/range+1];
for (int i = 0; i < buckets.length; i++) {
buckets[i]=new ArrayList();
}
//将数组元素分散到桶(元素值-min可以分配到对应桶且桶内元素只有一个,元素和桶具有映射关系
// ->和计数排序类似,这样保证了小桶装小元素,大桶装大元素,且只有一个元素
// 所以这样按顺序取桶元素,可以不用进行桶内排序,但空间浪费大)
for (int i : arr) {
//(除range约束多个元素为一组,减少桶数量,桶内有多个元素了,所以得进行桶内排序)
buckets[(i-min)/range].add(i);
}
int k=0;
for (ArrayList bucket : buckets) {
//桶内排序
bucket.sort(Comparator.comparingInt(o -> (Integer) o));
//将桶内元素放回原数组
for (Object o : bucket) {
arr[k]= (int) o;
k++;
}
}
}
- 基数排序:以下采用LDS,即从个位开始,从右向左对每一位进行排序。初始化[0 ~ 9]个桶,刚开始按个位大小将每个元素分散到对应的桶(个位为0的装入0号桶,以此类推),个位分散完之后,再按桶顺序取出元素写回原数组,再进行下一轮百位的排序,以此类推。
- 平均时间复杂度:O(k*n) (k位数,n元素个数)
- 空间复杂度:O(m) (m桶个数)
- 稳定性:稳定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
* 基数排序(LDS 从右向左)
*
* @param arr
*/
public void radixSort(int[] arr) {
if (arr.length == 0) {
return;
}
//初始化[0~9]个桶
ArrayList[] buckets = new ArrayList[10];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList();
}
//求最大值和最小值位数,位数大的为处理次数
int max = arr[0];
int min = arr[0];
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int maxBit = (max + "").length();
int minBit = (min + "").length() - 1;
int n = Integer.max(maxBit, minBit);
//个位->百位->千位···的顺序进行
int m = 1;
for (int i = 0; i < n; i++) {
//取数组元素分散到对应桶
for (int ele : arr) {
ele = ele - min;//负数也可以转换为>0的数,保证有桶可装
int j = ele / m % 10;
buckets[j].add(ele);
}
//按桶顺序将桶内元素取出放回原数组,进行下一轮分散到桶
int k = 0;
for (ArrayList bucket : buckets) {
for (Object ele : bucket) {
arr[k++] = (int) ele + min;//还原元素原始值
}
bucket.clear();//清空桶
}
m *= 10;
}
java中Arrays.sort()根据数据量不同和特性采用不同排序算法。
- 本文作者: zzr
- 本文链接: http://zzruei.github.io/2023/02b9b1def2.html
- 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
